#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int dx[3] = { 0, 1, 1 };
    int dy[3] = { 1, 0, 1 };
    vector<int> pathsWithMaxScore(vector<string>& board) {
        int n = board.size(), m = board[0].size(), mod = 1e9 + 7;
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(m, vector<int>(2, 0)));
        dp[n - 1][m - 1][1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            if (board[i][m - 1] == 'X') break;
            dp[i][m - 1][0] = dp[i + 1][m - 1][0] + board[i][m - 1] - '0', dp[i][m - 1][1] = dp[i + 1][m - 1][1];
        }
        for (int j = m - 2; j >= 0; j--) {
            if (board[n - 1][j] == 'X') break;
            dp[n - 1][j][0] = dp[n - 1][j + 1][0] + board[n - 1][j] - '0', dp[n - 1][j][1] = dp[n - 1][j + 1][1];
        }
        for (int i = n - 2; i >= 0; i--)
            for (int j = m - 2; j >= 0; j--) {
                if (board[i][j] == 'X') continue;
                for (int k = 0; k < 3; k++) {
                    int a = i + dx[k], b = j + dy[k];
                    if (dp[a][b][1] == 0) continue;
                    int tmp = dp[a][b][0] + (board[i][j] == 'E' ? 0 : board[i][j] - '0');
                    if (dp[i][j][0] < tmp) dp[i][j][0] = tmp, dp[i][j][1] = dp[a][b][1] % mod;
                    else if (dp[i][j][0] == tmp) dp[i][j][1] = (dp[i][j][1] + dp[a][b][1]) % mod;
                }
            }
        // for(int i = 0; i < n; i++)
        // {
        //     for(int j = 0; j < m; j++) cout << dp[i][j][0] << ' ';
        //     cout << endl;
        // }
        return dp[0][0];
    }
};